package java0329;

import java.util.*;

public class Main {
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
    }
}

class Solution {

    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            int val = map.getOrDefault(x, 0);
            map.put(x, val + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }

    // 力扣183.复制带随机指针的链表
    // 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
    // 该指针可以指向链表中的任何节点或空节点。
    // 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
    // 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
    // 并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
    // 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。
    // 那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }

    // 力扣771. 宝石与石头
    // 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。
    // S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    // J 中的字母不重复，J 和 S中的所有字符都是字母。
    // 字母区分大小写，因此"a"和"A"是不同类型的石头。
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        int ret = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i)) == true) {
                ret++;
            }
        }
        return ret;
    }

    // 力扣692. 前K个高频单词
    // 给一非空的单词列表，返回前 k 个出现次数最多的单词。
    // 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            int val = map.getOrDefault(words[i], 0);
            map.put(words[i], val + 1);
        }
        List<String> list = new ArrayList<>(map.keySet());
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (map.get(o1) == map.get(o2)) {
                    return o1.compareTo(o2);
                }
                return map.get(o2) - map.get(o1);
            }
        });
        return list.subList(0, k);
    }

    // 牛客网. 旧键盘
    // 链接：https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    //来源：牛客网
    //旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
    //肯定坏掉的那些键。
    //输入描述:
    //输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
    //以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
    //输出描述:
    //按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String excepted = scanner.next();
            String actual = scanner.next();
            excepted = excepted.toUpperCase();
            actual = actual.toUpperCase();
            // 不能这样写，因为输出顺序有要求
//            Map<Character, Integer> map = new HashMap<>();
//            for (int i = 0; i < excepted.length(); i++) {
//                char cur = excepted.charAt(i);
//                int val = map.getOrDefault(cur, 0);
//                map.put(cur, val + 1);
//            }
//            for (int i = 0; i < actual.length(); i++) {
//                char cur = actual.charAt(i);
//                int val = map.get(cur);
//                map.put(cur, val - 1);
//            }
//            StringBuilder stringBuilder = new StringBuilder();
//            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
//                if (entry.getValue() != 0) {
//                    stringBuilder.append(entry.getKey());
//                }
//            }
//            System.out.println(stringBuilder.toString());
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < actual.length(); i++) {
                set.add(actual.charAt(i));
            }
            Set<Character> badKey = new HashSet<>();
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < excepted.length(); i++) {
                char curKey = excepted.charAt(i);
                if (set.contains(curKey) == true) {
                    continue;
                }
                if (badKey.contains(curKey) == true) {
                    continue;
                }else {
                    badKey.add(curKey);
                    stringBuilder.append(curKey);
                }
            }
            System.out.println(stringBuilder.toString());
        }
    }
}
